/**
 * 面试题 05.01. 插入
 * https://leetcode-cn.com/problems/insert-into-bits-lcci/
 */
public class Solutions_mianshi_05_01 {
    public static void main(String[] args) {
//        int N = 1024, M = 19, i = 2, j = 6;  // output: 1100
        int N = 0, M = 31, i = 0, j = 4;  // output: 31

        int result = insertBits(N, M, i, j);
        System.out.println(result);
    }

    /**
     * 题目分析：“插入”操作，就是将 N 的 [i, j] 索引位上的位，全部置 0，最低位索引为 0，最高位索引为 31
     * M 最后需要左移 i 位
     * 最终用 M | N，得到最终的和
     */
    public static int insertBits(int N, int M, int i, int j) {
        while (j >= i) {
            int bit = 1 << j;
//            if (((N >> j) & 1) == 1) {
            if ((N & bit) == bit) {
                // 置 0 操作，即把 N >> j 上的位，变成位 0
                N -= bit;
            }
            j--;
        }
        // M 左移 i 位
        M = M << i;
        return N | M;
    }
}
